package com.xx.springboot.DataStructure.BST;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 实现 二分搜索树
 */
public class BST<E extends Comparable> {
    private class Node {
        private E data;
        private Node left, right;

        /**
         * 构造函数
         * @param data
         */
        public Node(E data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public BST() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 根节点
     */
    private Node root;

    /**
     * 二分搜索树 长度
     */
    private int size;

    /**
     * 获取的到二分搜索树长度
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断二分搜索树是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;// root == null
    }

    /**
     * 向二分搜索树 添加元素
     * @param e
     */
    public void add(E e) {
        this.root = add(root, e);
    }

    /**
     * 递归添加元素
     * @param root
     * @param e
     * @return
     */
    private Node add(Node root, E e) {
        if (root == null) {
            size++;
            root = new Node(e);
        }

        if(e.compareTo(root.data) > 0)
            root.right = add(root.right, e);
        else if(e.compareTo(root.data) < 0)
            root.left = add(root.left, e);

        return root;
    }

    /**
     * 判断树种是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 递归查找元素
     * @param root
     * @param e
     * @return
     */
    private boolean contains(Node root, E e) {
        if(root == null)
            return false;

        if(e.compareTo(root.data) == 0)
            return true;
        if(e.compareTo(root.data) > 0)
            return contains(root.right, e);
        else
            return contains(root.left, e);
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历 遍历以root为根的二分搜索树, 递归算法
     * @param root
     */
    private void preOrder(Node root) {
        if(root == null)
            return;

        System.out.println(root.data);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 前序遍历 非递归实现
     */
    public void preOrderNR() {

        if(root == null)
            return ;

        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node ret = stack.pop();
            System.out.println(ret.data);

            if(ret.right != null)
                stack.push(ret.right);
            if(ret.left != null)
                stack.push(ret.left);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    /**
     * 中序遍历 递归算法
     * @param root
     */
    private void inOrder(Node root) {
        if (root == null)
            return ;

        inOrder(root.left);
        System.out.println(root.data);
        inOrder(root.right);
    }

    /**
     * 中序遍历 非递归实现
     * @param root
     */
    public void inOrderNR(Node root) {
        if(root == root)
            return ;

        Stack<Node> stack = new Stack<>();

        Node cur = root;
        while (cur != null){

        }

    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node root) {
        if (root == null)
            return ;

        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.data);
    }

    /**
     * 层序遍历
     */
    public void levelOrder(){
        if(root == null)
            return ;

        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.data);

            if(cur.left != null)
                q.add(cur.left);
            else if (cur.right != null)
                q.add(cur.right);
        }
    }

    /**
     * 找到最小的元素
     * @return
     */
    public E minimum(){
        if(root == null)
            return null;

        Node minNode = minimum(root);
        return minNode.data;
    }

    /**
     * 递归查找二分搜索树中的最小元素
     * @param node
     * @return
     */
    private Node minimum(Node node){
        if(node.left == null)
            return node;

        return minimum(node.left);
    }

    /**
     * 删除二分搜索树种的最小元素
     * @return
     */
    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    /**
     * 递归删除最小的元素
     * @param node
     * @return
     */
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 删除最大的元素
     * @return
     */
    public E removeMax() {
        E ret = maxNode();
        root = removeMax(root);
        return ret;
    }

    /**
     * 递归删除最大的元素
     * @param node
     * @return
     */
    private Node removeMax(Node node){
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }


    public E maxNode(){
        if(root == null)
            return null;

        Node maxNode = maxNode(root);
        return maxNode.data;
    }

    /**
     * 递归查看二分搜索树的最大元素
     * @param node
     * @return
     */
    private Node maxNode(Node node){
        if(node.right == null)
            return node;

        return maxNode(node.right);
    }





    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    /**
     * <p>
     *     创建 二分搜索树的 字符串输出
     * </p>
     * @param root 根节点
     * @param depth 深度
     * @param res 要处理的StringBuffer
     */
    private void generateBSTString(Node root, int depth, StringBuffer res) {
        if (root == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + root.data + "\n");
        generateBSTString(root.left, depth + 1, res);
        generateBSTString(root.right, depth + 1, res);
    }

    /**
     * <p>
     *     根据深度打印对应的字符串
     * </p>
     * @param depth
     * @return
     */
    private String generateDepthString(int depth) {
        StringBuffer res = new StringBuffer();
        for (int i = 0 ; i < depth ; i++) {
            res.append("--");
        }
        return res.toString();
    }

    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums)
            bst.add(num);

        System.out.println("前序遍历");
        bst.preOrder();

        System.out.println("中序遍历");
        bst.preOrderNR();

        System.out.println(bst);

    }
}
